package com.wuxuan.algorithm_homework.unionFind;

/**
 * 并查集
 * <p>
 * 基本操作
 * 初始化
 * 在使用并查集之前，需要对其进行初始化。通常将每个元素初始化为一个独立的集合，即每个元素的父节点指向自身。
 * <p>
 * 查找(Find)
 * 查找操作用于确定一个元素所属的集合，通过不断沿着父节点指针向上查找，直到找到根节点。根节点代表了该元素所属的集合。
 * <p>
 * 合井(Union)
 * 合并操作将两个元素所在的集合合并为一个集合。具体做法是将其中一个集合的根节点的父节点指向另一个集合的根节点。
 */
public class UnionFind {
    private int[] parent;

    //初始化并查集
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int findRoot(int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        // x == parent[x] ,说明当前节点为根节点
        return x;
    }

    public void union(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

    //判断元素 x 和 y 是否属于同一个集合
    public boolean connected(int x, int y) {
        return findRoot(x) == findRoot(y);
    }
}
